package cn.kent.middle;


/**
 * 74. 搜索二维矩阵
 */
public class SearchMatrix {
    public static void main(String[] args) {

    }

    /**
     * 二分法
     */
    public static boolean searchMatrix2(int[][] matrix, int target) {
        // 先求出整个数组的长度，然后看做一个一维数组，进行二分
        int r = matrix[0].length * matrix.length;
        int l = 0;
        while (l <= r) {
            int mid = (r + l) / 2;
            if (matrix[mid / matrix[0].length][mid % matrix[0].length] == target)
                return true;
            else if (matrix[mid / matrix[0].length][mid % matrix[0].length] < target)
                l = mid + 1;
            else if (matrix[mid / matrix[0].length][mid % matrix[0].length] > target)
                r = mid - 1;
        }
        return false;
    }

    /**
     * 暴力搜索
     * 双层for循环
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] ints : matrix) {
            for (int anInt : ints) {
                if (anInt == target) return true;
            }
        }
        return false;
    }
}
